GRE: A Graph Runtime Engine for Large-Scale Distributed Graph-Parallel Applications

摘要

Large-scale distributed graph-parallel computing is challenging. On one hand,due to the irregular computation pattern and lack of locality, it is hard toexpress parallelism efficiently. On the other hand, due to the scale-freenature, real-world graphs are hard to partition in balance with low cut. Toaddress these challenges, several graph-parallel frameworks including Pregeland GraphLab (PowerGraph) have been developed recently. In this paper, wepresent an alternative framework, Graph Runtime Engine (GRE). While retainingthe vertex-centric programming model, GRE proposes two new abstractions: 1) aScatter-Combine computation model based on active message to exploit massivefined-grained edge-level parallelism, and 2) a Agent-Graph data model based onvertex factorization to partition and represent directed graphs. GRE isimplemented on commercial off-the-shelf multi-core cluster. We experimentallyevaluate GRE with three benchmark programs (PageRank, Single Source ShortestPath and Connected Components) on real-world and synthetic graphs of millionsbillion of vertices. Compared to PowerGraph, GRE shows 2.5~17 times betterperformance on 8~16 machines (192 cores). Specifically, the PageRank in GRE isthe fastest when comparing to counterparts of other frameworks (PowerGraph,Spark,Twister) reported in public literatures. Besides, GRE significantlyoptimizes memory usage so that it can process a large graph of 1 billionvertices and 17 billion edges on our cluster with totally 768GB memory, whilePowerGraph can only process less than half of this graph scale.